package main;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeMap;

import tree.Tree;
import utils.DecreasingComparator;
import utils.DegreeVector;
import utils.ListPair;

/**
 * An object that holds a list of DegreeVectors (of size 2) and various methods for attempting to construct a graph
 * given by those vectors.
 * @author Alex Dusenbery
 * @version 1.0
 *
 */
public class DegreeSequenceBisection<T> {
	
	public static final double REQUIRED_BIPARTITE_RATIO = 0.90;
	public static final int NUM_SUBSET_SUM_TRIES = 0;
	private DecreasingComparator<DegreeVector> DECREASING_COMPARATOR = new DecreasingComparator<DegreeVector>();
	private List<DegreeVector> sortedList;
	private int oppositeBlockIndex = 1;
	public static final double APPROXIMATION_PARAMETER = 0.25;
	private double numberEdges;
//	private List<DegreeVector<T>> leftVectors, rightVectors;

	/**
	 * Constructs a new object to try to determine if, given a set of bivectors, there exists a 
	 * graph given by the degree sequence described by those vectors.
	 */
	public DegreeSequenceBisection(List<DegreeVector> vectors) {
		sortedList = new ArrayList<DegreeVector>();
		sortedList.addAll(vectors);
		Collections.sort(sortedList, DECREASING_COMPARATOR);
		this.numberEdges = sumDegreeVectorList(sortedList, 0) + sumDegreeVectorList(sortedList, 1);
		this.numberEdges /= 2;
	}
	
	/**
	 * This method linearly scans the underlying sorted list and looks for points at which the list can be split in two,
	 * such that the sum of the first entries of one block equals the sum of the second entries of the opposite block.
	 * @return A list of possible splitting points of the sorted list.
	 */
	public List<Integer> getPossibleSplittingPoints() {
		List<Integer> result = new ArrayList<Integer>();
		for(int i = 1; i < sortedList.size(); i++) {
			//find the sum of the left top and bottom row
			double topLeft = 0.0, bottomLeft = 0.0;
			for(int j = 0; j < i; j++) {
				topLeft += (Double)sortedList.get(j).getEntry(0);
				bottomLeft += (Double)sortedList.get(j).getEntry(1);
			}
			
			//find the sum of the right top and bottom row
			Double topRight = 0.0, bottomRight = 0.0;
			for(int j = i; j < sortedList.size(); j++) {
				topRight += (Double)sortedList.get(j).getEntry(0);
				bottomRight += (Double)sortedList.get(j).getEntry(1);
			}
			
			//see if either top right matches bottom left of vica versa
			if(topRight.equals(bottomLeft) || bottomRight.equals(topLeft))
				result.add(i);
		}
		return result;
	}
	
	/**
	 * Moves the first element of sortedList to the end of the list.
	 */
	public void moveFrontToBack() {
		DegreeVector temp = sortedList.remove(0);
		sortedList.add(temp);
	}
	
	/**
	 * Sorts the elements in sortedList according to the maximum element of each bi-vector.
	 */
	public void sortByMaxElement() {
		Comparator<DegreeVector> maxElementComp = new Comparator<DegreeVector>() {
			@Override
			public int compare(DegreeVector v1, DegreeVector v2) {
				return -((Double)Math.max((Double)v1.getEntry(0), (Double)v1.getEntry(1))).compareTo(
						Math.max((Double)v2.getEntry(0), (Double)v2.getEntry(1)));
			}
		};
		Collections.sort(sortedList, maxElementComp);
	}
	
	/**
	 * This method sorts the main sortedList according to the specified index of the DegreeVectors inside the list.
	 * @param index The index used to sort the degree vectors.
	 * @param descending True if the elements should be in non-increasing order, false otherwise.
	 */
	public void sortByElement(final int index, boolean descending) {
		final int sign = (descending ? -1 : 1);
		Comparator<DegreeVector> indexComp = new Comparator<DegreeVector>() {
			
			@Override
			public int compare(DegreeVector o1, DegreeVector o2) {
				return sign*(o1.getEntry(index).compareTo(o2.getEntry(index)));
			}
		};
		Collections.sort(sortedList, indexComp);
	}

	/**
	 * @return the sortedList
	 */
	public List<DegreeVector> getSortedList() {
		return sortedList;
	}
	
	/**
	 * This method tries to find a set of bipartite splittings for the sortedList.  It first sorts the list by
	 * the index which indicates degree to the opposite block in the Degree Vectors.  Next, it iterates through that list
	 * and assigns each DegreeVector to the left or right block in a way such that the difference between degrees of both
	 * blocks is kept at a minimum (i.e. in a greedy manner).  This step is performed as many times as the length of the
	 * sortedList.  At the end of each of these tries, the first list element is moved to the end of the list before repetition.
	 * Furthermore, at the end of each iteration and before moving the first element to the end of the list, an attempt
	 * is made to find a bipartite subgraph using the subset-sum approximation algorithm, if certain conditions are met 
	 * (i.e. a certain percentage of splittings has not been found, and the number of previous calls to the subset-sum
	 * algorithm does not exceed a predefined limit).
	 * @param tryEvenSplit Set this to true only if you want to try splitting the list into two equal-sized parts, 
	 * by iterating over the sorted list and alternately assigning each DegreeVector to the left and right blocks. It
	 * doesn't work very well. 
	 * @return A set of ListPairs of DegreeVectors representing a bipartite subgraph.
	 */
	public Set<ListPair<DegreeVector>> findBipartiteSplitting(boolean tryEvenSplit) {
		Set<ListPair<DegreeVector>> resultSet = new HashSet<ListPair<DegreeVector>>();
		sortByElement(oppositeBlockIndex, true);
		List<DegreeVector> left;
		List<DegreeVector> right;
		
		DPSolver solver = new DPSolver(sortedList, oppositeBlockIndex);
		boolean[][] memo = solver.memoizeSequence();
		Tree<Integer> tree = solver.getAllPartitions(memo);
		Set<BitSet> solutions = solver.getSolutions();
		solver.printTable(memo);
		int bitsLength = solver.getSequence().size();

		for (BitSet set : solutions) {
			left = new ArrayList<DegreeVector>();
			right = new ArrayList<DegreeVector>();
			for (int bit = 0; bit < bitsLength; bit++) {
				if (set.get(bit))
					left.add(sortedList.get(bit));
				else
					right.add(sortedList.get(bit));
			}
			ListPair<DegreeVector> pair = new ListPair<DegreeVector>(left,
					right);
			resultSet.add(pair);
		}
		return resultSet;
	}

	/**
	 * @param resultSet
	 * @param left
	 * @param right
	 */
	private double tryGreedyAssignment(Set<ListPair<DegreeVector>> resultSet,
			List<DegreeVector> left, List<DegreeVector> right) {
		boolean found;
		double difference = 0;
		for (int i = 0; i < sortedList.size(); i++) {
			difference = sumDegreeVectorList(left, oppositeBlockIndex)
					- sumDegreeVectorList(right, oppositeBlockIndex);
			if (difference <= 0)
				left.add(sortedList.get(i));
			else
				right.add(sortedList.get(i));
		}
		if (difference == 0) {
			found = true;
			resultSet.add(new ListPair<DegreeVector>(left, right));
		}
		return difference;
	}
	
	private Set<ListPair<DegreeVector>> extractDifferentSubsets(
			TreeMap<Double, Double> multiplicity, ListPair<DegreeVector> pair) {
		for(DegreeVector dv : pair.getLeftList()) {
			Double leftMult = multiplicity.get(dv.getEntry(oppositeBlockIndex));
			if(leftMult > 1) {
				
			}
		}
		return null;
	}
	
	private List<DegreeVector> findMatchingMultiplicity(Double target, TreeMap<Double, Double> multiplicity, List<DegreeVector> list) {
		return list;
		
	}

	/**
	 * @param resultSet
	 * @param left
	 * @param right
	 */
	private void tryEvenSplit(Set<ListPair<DegreeVector>> resultSet,
			List<DegreeVector> left, List<DegreeVector> right) {
		for (int i = 0; i < sortedList.size(); i++) {
			if (i % 2 == 0)
				left.add(sortedList.get(i));
			else
				right.add(sortedList.get(i));
		}
		double leftSum = sumDegreeVectorList(left, oppositeBlockIndex);
		double rightSum = sumDegreeVectorList(right, oppositeBlockIndex);
		if (leftSum == rightSum)
			resultSet.add(new ListPair<DegreeVector>(left, right));
		else {
			//find move of one degree vector to opposite list that will minimize the difference
		}
	}

	/**
	 * This method takes two lists of Degree Vectors that do not make a bipartite subgraph and uses the subset sum
	 * approximation algorithm to swap elements of the list so that a bipartition is formed.  If such a swapping is found, 
	 * two new lists with the appropriate degree vectors are wrapped in a ListPair object and returned.  Otherwise,
	 * null is returned.
	 * @param leftInput
	 * @param rightInput
	 * @return
	 */
	private ListPair<DegreeVector> getBipartiteUsingSubsetSum(List<DegreeVector> leftInput,
			List<DegreeVector> rightInput) {
		List<DegreeVector> left = new ArrayList<DegreeVector>();
		List<DegreeVector> right = new ArrayList<DegreeVector>();
		left.addAll(leftInput);
		right.addAll(rightInput);
		ListPair<DegreeVector> pair = null;
		
		boolean sumFound = false;
		List<Double> degrees = new ArrayList<Double>();
		double target = sumDegreeVectorList(left, oppositeBlockIndex)
					- sumDegreeVectorList(right, oppositeBlockIndex);
		if(target < 0) {
			for(DegreeVector dv : left)
				degrees.add(-dv.getEntry(oppositeBlockIndex));
			for(DegreeVector dv : right)
				degrees.add(dv.getEntry(oppositeBlockIndex));
		}
		else {
			for(DegreeVector dv : left)
				degrees.add(dv.getEntry(oppositeBlockIndex));
			for(DegreeVector dv : right)
				degrees.add(-dv.getEntry(oppositeBlockIndex));
		}
		List<Double> swapList = approxSubsetSum(degrees, target, APPROXIMATION_PARAMETER);
		if(swapList.get(swapList.size() - 1) == target)	{
			//then a swap that will yield a bipartite splitting is found.
			sumFound = true;
			List<DegreeVector> swapLeftToRight = new ArrayList<DegreeVector>();
			List<DegreeVector> swapRightToLeft = new ArrayList<DegreeVector>();
			
			for(int i = 0; i < swapList.size() - 1; i++) {
				Double entry = swapList.get(i);
				DegreeVector dv = null;
				if(target < 0) {
					//negative values will be in left list only
					if(entry < 0) {
						dv = findDegreeVectorEntry(left, -entry, oppositeBlockIndex);
						swapLeftToRight.add(dv);
					}
					else {
						dv = findDegreeVectorEntry(right, entry, oppositeBlockIndex);
						swapRightToLeft.add(dv);
					}
				}
				else {
					//negative values are in right list only
					if(entry < 0) {
						dv = findDegreeVectorEntry(right, -entry, oppositeBlockIndex);
						swapRightToLeft.add(dv);
					}
					else {
						dv = findDegreeVectorEntry(left, entry, oppositeBlockIndex);
						swapLeftToRight.add(dv);
					}
				}
			}
			left.removeAll(swapLeftToRight);
			right.removeAll(swapRightToLeft);
			left.addAll(swapRightToLeft);
			right.addAll(swapLeftToRight);
		}
		if(sumFound)
			pair = new ListPair<DegreeVector>(left, right);
		return pair;
	}
	
	/**
	 * This method takes two lists of degree vectors and uses them to construct a list of numbers.  The difference
	 * between their out degrees is used as the target number.  
	 * @param left
	 * @param right
	 * @param approxParam Must be between 0 and 1, exclusive.
	 * @return
	 */
	public List<Double> approxSubsetSum(List<Double> set, double target, double approxParam) {
		int n = set.size();
		List<Double> last = new ArrayList<Double>();
		last.add(0.0);
		for(int i = 0; i < n; i++) {
			List<Double> current = mergeLists(last, listIncrement(last, set.get(i)));
			current = trim(current, (approxParam/(2*n)));
			List<Double> toRemove = new ArrayList<Double>();
			for(Double d : current) {
				if(d > target)
					toRemove.add(d);
			}
			current.removeAll(toRemove);
			toRemove.clear();
			last = current;
		}
		return last;
	}
	
	/**
	 * Sums each of the entries of a given index of a list of DegreeVector objects.
	 * @param vectors
	 * @param index
	 * @return The above sum.
	 */
	private double sumDegreeVectorList(List<DegreeVector> vectors, int index) {
		double sum = 0;
		for(DegreeVector dv : vectors)
			sum += dv.getEntry(index);
		return sum;
	}
	
	/**
	 * Looks through a list of degree vectors for a given entry in the specified index.  Once it finds a match,
	 * that degree vector is returned.
	 * @param list
	 * @param entry
	 * @param index
	 * @return
	 */
	private DegreeVector findDegreeVectorEntry(List<DegreeVector> list, Double entry, int index) {
		DegreeVector result = null;
		for(DegreeVector dv : list) {
			if(dv.getEntry(index).equals(entry))
				result = dv;
		}
		return result;
	}
	
	/**
	 * This trims a list L = <y1,y2,...,ym>, assuming L is sorted in monotonically increasing order.
	 * @param list
	 * @param delta
	 * @return A trimmed, sorted list.
	 */
	public List<Double> trim(List<Double> list, double delta) {
		Collections.sort(list);
		int m = list.size();
		List<Double> result = new ArrayList<Double>();
		result.add(list.get(0));
		double last = list.get(0);
		for(int i = 1; i < m; i++) {
			double y = list.get(i);
			if(y > (last * (1 + delta))) {
				result.add(y);
				last = y;
			}
		}
		Collections.sort(result);
		return result;
	}
	
	/**
	 * This method returns the sorted list that is the merge of its two sorted input lists, with
	 * duplicate entries removed.
	 * @param list1
	 * @param list2
	 * @return
	 */
	public List<Double> mergeLists(List<Double> list1, List<Double> list2) {
		Collections.sort(list1);
		Collections.sort(list2);	//ensure these are sorted in monotonically increasing order.
		Set<Double> set = new HashSet<Double>();
		set.addAll(list1);
		set.addAll(list2);
		List<Double> result = new ArrayList<Double>();
		result.addAll(set);
		Collections.sort(result);
		return result;
	}
	
	/**
	 * Given a list (of doubles), this method increments each entry of the list by the amount x.
	 * @param list
	 * @param x
	 * @return A new list, with each entry of the original incremented by x.
	 */
	private List<Double> listIncrement(List<Double> list, double x) {
		List<Double> result = new ArrayList<Double>();
		Double entry = 0.0;
		for(Double d : list) {
			entry = d;
			entry += x;
			result.add(entry);
		}
		return result;
	}
	
	/**
	 * Returns the maximum value in a list of Doubles.
	 * @param list
	 * @return
	 */
	private double listMax(List<Double> list) {
		double max = Double.NEGATIVE_INFINITY;
		for(Double d : list) {
			if(d > max)
				max = d;
		}
		return max;
	}
}
